Biuro podróży
Limit pamięci: 32 MB
W ostatnim czasie mieszkańcy Bajtocji zaczęli podróżować częściej niż
dotychczas. Przedsiębiorczy Bajtazar wpadł na pomysł otwarcia biura
podróży. Już pierwszego dnia urzędowania do biura zgłosiło się klientów
(na potrzeby naszego zadania możemy ich ponumerować liczbami
naturalnymi od do ), którzy chcą pojechać na wycieczkę.
Niestety każdy z nich ma swoje wymagania.
Twoim zadaniem jest pomóc Bajtazarowi w wybraniu klientów, którzy
pojadą na wycieczkę, tak aby zmaksymalizować zysk Bajtazara.
Każdy klient określił, ile wynosi dla niego wartość wycieczki organizowanej przez
Bajtazara. Niech będzie taką wartością dla klienta
().
Jeśli , to klient zapłaci bajtockich dolarów,
aby pojechać na wycieczkę, jeśli natomiast ,
to aby klient pojechał na wycieczkę, Bajtazar musi mu
dopłacić bajtockich dolarów.
Klienci oprócz wymagań finansowych posiadają również wymagania towarzyskie.
Klient ma () takich wymagań,
-te wymaganie -tego klienta jest reprezentowane przez parę
liczb całkowitych ()
().
Wymaganie to należy rozumieć tak, że aby klient
pojechał na wycieczkę, to na wycieczkę musi pojechać również klient
lub koszt wycieczki dla klienta musi zostać obniżony o
bajtockich dolarów (może się zdarzyć, że koszt wycieczki dla pewnych klientów
z dodatniego stanie się ujemny, co spowoduje, że Bajtazar będzie musiał dopłacić tym
klientom, żeby wzięli oni udział w wycieczce, rekompensując tym samym brak zaspokojenia
ich wymagań towarzyskich).
Pomóż Bajtazarowi wybrać grupę klientów, których ma zabrać na wycieczkę, tak
aby zmaksymalizować jego zysk (liczba miejsc na wycieczce jest
nieograniczona).
Zadanie
Dysponujesz jedenastoma zestawami danych, które możesz ściągnąć stąd.
Każdy zestaw jest zapisany w osobnym pliku biu.in, gdzie
to numer zestawu (). Rozwiązaniem zadania powinien być
program, który wczytuje ze standardowego wejścia jedną liczbę
całkowitą , i wypisuje na standardowe wyjście
odpowiedź dla -tego zestawu.
Rozwiązanie zestawu biu0.in nie jest
punktowane.
W pierwszym wierszu odpowiedzi powinna się znajdować dokładnie jedna liczba całkowita ()
- liczba klientów, których Bajtazar powinien zabrać na wycieczkę.
Jeśli liczba jest dodatnia, w drugim wierszu powinno się znaleźć
liczb całkowitych, oddzielonych pojedynczymi odstępami,
będących numerami klientów, których Bajtazar powinien zabrać na wycieczkę.
Jeśli istnieje wiele optymalnych rozwiązań to możesz podać dowolne z nich.
Numery klientów mogą być umieszczone w wyjściu w dowolnej kolejności.
Opis pojedynczego pliku wejściowego
W pierwszym wierszu znajduje się dokładnie jedna liczba całkowita ()
oznaczająca liczbę klientów biura podróży.
W kolejnych wierszach opisani są poszczególni klienci.
W -wszym wierszu () znajdują się liczby całkowite
() oraz (),
a za nimi par liczb całkowitych ,
()
- wszystkie liczby w wierszu
oddzielone są pojedynczymi odstępami. Możesz założyć, że każdy klient ma co najwyżej
jedno wymaganie towarzyskie dotyczące dowolnego innego klienta.
Przykład
Dla danych wejściowych:
4
5 0
6 2 1 10 3 1
-10 0
1 2 1 10 2 10
poprawną odpowiedzią jest:
3
1 2 4
Jeśli Bajtazar wybierze klientów , to osiągnie zysk bajtockich dolarów,
co jest rozwiązaniem optymalnym.
Autor zadania: Marek Cygan.